package com.lw.leetcode.binary.b;

import java.util.Arrays;

/**
 * create by idea
 * binary
 * 面试题 16.06. 最小差
 *
 * @author lmx
 * @version 1.0
 * @date 2022/1/3 16:56
 */
public class SmallestDifference {

    public static void main(String[] args){
        SmallestDifference test = new SmallestDifference();

        // 3
//        int[] a = {23, 127, 235, 19, 8};
//        int[] b = {1, 3, 15, 11, 2};
        // 1
        int[] a = {-2147483648,1};
        int[] b = {2147483647,0};

        int i = test.smallestDifference(a, b);
        System.out.println(i);

    }

    public int smallestDifference(int[] a, int[] b) {

        int l1 = a.length;
        int l2 = b.length;
        int[] m;
        if (l1 < l2) {
            m = a;
            a = b;
        } else {
            m = b;
            l2 = l1;
        }

        Arrays.sort(m);

        long min = Integer.MAX_VALUE;
        for (int i = 0; i < l2; i++) {
            int v = a[i];

            if (binary1(m, v) != -1) {
                return 0;
            }

            int index = binary2(m, v) ;
            if (index != -1) {
                min = Math.min(min,(long)v - m[index]);
            }
            index = binary3(m, v) ;
            if (index != -1) {
                min = Math.min(min, m[index] - (long)v);
            }
        }

        return (int) min;
    }

    /**
     * 查找目标值
     *
     * @param nums   数组
     * @param target 目标值
     * @return 索引下标
     */
    public int binary1(int[] nums, int target) {
        int st = 0;
        int end = nums.length - 1;
        while (st <= end) {
            int m = st + ((end - st) >> 1);
            if (nums[m] < target) {
                st = m + 1;
            } else if (nums[m] > target) {
                end = m - 1;
            } else {
                return m;
            }
        }
        return -1;
    }

    /**
     * 小于target的最大值
     *
     * @param nums   数组
     * @param target 目标值
     * @return 索引下标
     */
    public int binary2(int[] nums, int target) {
        if (nums[0] >= target) {
            return -1;
        }
        int st = 0;
        int end = nums.length - 1;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            if (nums[m] < target) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return st;
    }

    /**
     * 大于target的最小值
     *
     * @param nums   数组
     * @param target 目标值
     * @return 索引下标
     */
    private int binary3(int[] nums, int target) {
        int end = nums.length - 1;
        if (nums[end] <= target) {
            return -1;
        }
        int st = 0;
        while (st < end) {
            int m = st + ((end - st) >> 1);
            if (nums[m] > target) {
                end = m;
            } else {
                st = m + 1;
            }
        }
        return st;
    }

}
